\rsec{PageRank}

O \textit{PageRank} foi o alvo principal de estudos neste trabalho. Por
alavancar uma das maiores empresas do segmento de computação do mundo, a Google,
é pertinente atribuir um pouco mais de atenção ao método.

\rssec{História}

Antes de 1998, não haviam mecanismos de busca que levavam em conta a estrutura
de \textit{hyperlinks} da rede, no entanto, alguns pesquisadores, como Larry
Page e Sergey Brin já tinham ideias de como retirar informações desta estrutura
da web.

O PageRank foi desenvolvido na Universidade de Stanford como parte de um
protótipo de um mecanismo de busca textual em páginas da web chamado \textit{Google}
\cite{Anatomy}, que usa de maneira crucial a estrutura de links das páginas.

Este protótipo foi a base para o \textit{Google} que conhecemos hoje. O endereço
original: \href{http://google.stanford.edu/}{\texttt{google.stanford.edu}} ainda
existe, e hoje é o mecanismo de busca oficial da Universidade de Stanford. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Ideia}

A ideia do \textit{PageRank} consiste em considerar cada hyperlink como sendo
uma recomendação, isto é, um link de uma página para outra significa que a
primeira serve como um aval para a segunda, portanto, uma página com mais
recomendações, provavelmente, é mais importante que uma outra com menos
recomendações.

No entanto, devemos também levar em conta a fonte da recomendação, pois
dependendo da onde ela veio, pode ser mais relevante. Por exemplo, uma
recomendação de \textit{Donald Knuth} para uma página sobre algoritmos parece ser mais
importante do que uma recomendação dele para uma página sobre esportes. Por
outro lado, se descobrirmos que o \textit{Donald Knuth} é uma pessoa muito gentil e 
recomenda muitas páginas sobre algoritmos, então o valor desta recomendação
deve ser menor que o esperado.

Resumidamente, é assim que o \textit{PageRank} funciona: ``uma página é
importante se ela é recomendada por outras páginas importantes''.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Abstração}

Para entender como o \textit{PageRank} funciona, descreveremos as ações de um
usuário ``especial'': o \textit{Random Surfer}.

O \textit{random surfer} faz o papel de um usuário com ações aleatórias, que
clica, com probabilidade uniforme, em algum link da página que ele se encontra,
assim dirigindo-se para outra página e repetindo o processo. A estrutura pura de
\textit{links} está descrita posteriormente pela matriz $H$, onde $H_{ij}$
representa a probabilidade de ele usar um \textit{link} para ir da sua página
atual $i$ para a página $j$. É interessante notar, que se uma página é visitada
mais vezes pelo \textit{random surfer} do que outras, significa que existe na
estrutura da web uma quantidade grande de caminhos chegando nela. Ou seja,
quanto mais vezes o \textit{random surfer} passar em uma página, mais importante
ela deve ser.

Eventualmente, dependendo da estrutura dos \textit{links}, o
\textit{random surfer} pode cair em uma página que não possua nenhuma outra como
referência, chamada de \textit{dangling node}, o que interromperia o processo
de navegar aleatoriamente na internet. Quando isso ocorrer, seria ideal que o
\textit{random surfer} escolhesse qualquer página da internet para continuar o
processo. Isso pode ser observado com a transição da matriz $H$ para $S$, onde
as páginas sem \textit{links}, indiretamente, apontam para todas as outras.

\begin{center}
\includegraphics[scale=0.4]{grafo_exemplo_dn.png}\\
\scriptsize{Figura 3.1: \textit{Dangling node}, uma página sem \textit{links}.}
\end{center}

Para deixar o cenário um pouco mais realista (e também solucionar o problema dos
\textit{rank sinks} com ciclos), o \textit{random surfer} pode eventualmente
desistir de escolher um \textit{link} da sua página atual e começar o processo
novamente por outra página qualquer. A probabilidade $\alpha$ representa a
probabilidade do \textit{random surfer} continuar seguindo a estrutura original
da internet e $1 - \alpha$ a probabilidade dele escolher qualquer outra página
para começar novamente o processo.
Essa nova matriz de probabilidade é descrita em $G$.

\begin{center}
\includegraphics[scale=0.4]{grafo_exemplo_ciclo.png}\\
\scriptsize{Figura 3.2: Conjunto de páginas que formam um \textit{ciclo}.}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Definição}

A primeira fórmula, apresentada em \cite{PageRank}, define o \textit{PageRank}
de uma página $P_i$, denotado como $r(P_i)$, como:

$$ r(P_i) = \sum_{P_j \in B_{P_i}} \frac{r(P_j)}{|P_j|} $$ 

Onde $B_{P_i}$ é o conjunto das páginas que apontam para $P_i$ e $|P_j|$ é o 
número de links contidos em $P_j$.

De uma maneira intuitiva, ela tenta descrever que quanto mais referências uma
página possuir, maior o seu \textit{rank}, e mais ainda, se for referenciada por
uma página muito importante, o seu \textit{rank} será maior ainda.

Podemos ver que a definição é recursiva, se estendendo por todo o conjunto de
páginas analisadas, e, eventualmente, para calcular o \textit{rank} de uma
página, recaímos na necessidade de saber o seu rank.

A representação matricial nos permite mudar um pouco a abstração e entrar no
universo dos processos estocásticos, mais precisamente abordando as cadeias de
Markov. Podemos imaginar que cada página representa um estado da cadeia, e cada
\textit{link} representa uma aresta de transição entre estados, então nos
faltaria somente atribuir as probabilidades de transição entre eles. Caso
conseguíssemos, teríamos uma matriz $A$ de probabilidade tal que:

$$
\pi' = \pi'A
$$
onde $\pi_i$ é o valor do \textit{rank} atribuído à página $P_i$.

A fórmula pode ser interpretada como a distribuição estacionária de uma cadeia
de Markov. O vetor $\pi$ indica a probabilidade de se estar no estado $i$ (ou no
caso, na página $P_i$ após infinitas mudanças de estado. É claro que para isso
teríamos que possuir em mãos uma matriz $A$ moldada e com algumas propriedades
para a obtenção do vetor estacionário.

Além do ponto de vista estocástico, podemos também imaginar a matriz $A$ como
uma transformação linear. O vetor $\pi$, neste caso, representa o autovetor da
transformação linear associado ao autovalor 1.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Primeira Representação Matricial: H}

Podemos tentar fazer uma adaptação da matriz $L$ para que se pareça um pouco
mais com uma matriz de transição de um processo estocástico. Tentaremos então
atribuir um pouco de probabilidade nos valores não nulos de $L$, assim obtendo a
seguinte matriz $H$.

$$
H_{ij} = \begin{cases} 
            1/|P_i|, & \mbox{se existe um arco ligando } i\mbox{ a } j\\
            0, & \mbox{caso contrário}
         \end{cases} 
$$
onde $|P_i|$ é o número de \textit{links} contidos em $P_i$.

Podemos perceber também que $H$ é muito parecida com uma
\textit{matriz estocástica}, excetuando as linhas cujas entradas são todas
nulas. Estas linhas são geradas por páginas que não possuem nenhuma outra como
referência, e, no contexto do grafo da web, são chamadas de
\textit{dangling nodes}. Com alguns ajustes, podemos utilizá-la como a matriz de
transição $A$, descrita na subseção anterior, então temos:

$$
\pi' = \pi'H
$$

A partir da fórmula acima, podemos observar que a complexidade de cada iteração
do algoritmo é $O(n^2)$, dado a multiplicação matriz-vetor. Entretanto, a matriz
$H$ é esparsa, e apenas suas entradas não-nulas são armazenadas. Segundo
\cite{PageRank-Beyond}, a média de links é de aproximadamente 10 por página.
Mais especificamente, $H$ possui algo próximo de $10n$ entradas não-nulas, ao
contrário de $n^2$ de uma matriz densa. Dessa maneira, a complexidade da iteração é
da ordem de $O(n)$.

\begin{center}
\includegraphics[scale=0.3]{sparse_matrix.png}\\
\scriptsize{Figura 3.3: Matriz esparsa. Os pixels brancos representam entradas
não nulas.}
\end{center}

Devemos contornar um problema proveniente da modelagem escolhida: os
\textit{rank sinks}, que são páginas que acumulam \textit{rank}, não
redistribuindo para outras páginas. Existem dois tipos de \textit{rank sink}: os
\textit{dangling nodes}, que são um \textit{rank sink} contendo uma única
página, e os ciclos, que repassam \textit{rank} entre si, formando um subgrupo
de páginas que não repassam \textit{rank} para as outras.

Tendo como exemplo o grafo da figura 2.2, temos a seguinte matriz $H$ que
representa sua estrutura modificada pelas probabilidades de escolha dos
\textit{links} em cada página:


$$
H = \begin{pmatrix} 0 & 1/2 & 1/2 & 0 & 0 & 0\\
                    0 & 0 & 0 & 0 & 0 & 0\\
                    1/3 & 1/3 & 0 & 0 & 1/3 & 0\\
                    0 & 0 & 0 & 0 & 1/2 & 1/2\\
                    0 & 0 & 0 & 1/2 & 0 & 1/2\\
                    0 & 0 & 0 & 1 & 0 & 0\end{pmatrix}
$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Segunda Representação Matricial: S}

Para corrigir o problema dos \textit{dangling links}, é feito um ajuste
na matriz $H$. As linhas nulas em $H$ serão substituídas pelo vetor
$(1/n)e'$, gerando uma nova matriz que chamaremos de $S$, que agora é
estocástica. Podemos expressar $S$ em função de $H$, visto que a
mudança que ocorre de uma matriz para outra é a adaptação das linhas nulas.
Temos então:

$$
S = H + a((1/n)e')
$$
onde $e$ é um vetor com valor 1 em todas as suas entradas.

O vetor binário $a$ é chamado \textit{dangling node vector}. O ajuste garante
que $S$ é estocástica, e então, uma matriz de transição de probabilidade para
uma cadeia de Markov.

$$
a_i = \begin{cases}
        1, & \mbox{se a } i\mbox{-ésima linha de } H\mbox{ for nula}\\
        0, & \mbox{caso contrário}
      \end{cases} 
$$

Tomando como exemplo o grafo da figura 2.2, temos a matriz $S$, derivada da
matriz $H$, sem o \textit{dangling node} correspondente ao vértice 2:

$$
S = \begin{pmatrix} 0 & 1/2 & 1/2 & 0 & 0 & 0\\
                    1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\
                    1/3 & 1/3 & 0 & 0 & 1/3 & 0\\
                    0 & 0 & 0 & 0 & 1/2 & 1/2\\
                    0 & 0 & 0 & 1/2 & 0 & 1/2\\
                    0 & 0 & 0 & 1 & 0 & 0\end{pmatrix}
$$

E a representação do mesmo grafo com as arestas que surgiram após o ajuste da
matriz $S$:

\begin{center}
\includegraphics[scale=0.4]{grafo_exemplo_s.png}\\
\scriptsize{Figura 3.4: Grafo da figura 2.2 após as mudanças da matriz $H$ para
$S$.}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Terceira Representação Matricial: G}

Apesar das mudanças estocásticas que levaram a matriz $H$ à matriz $S$, os
resultados de convergência para o vetor $\pi$ ainda não são garantidos.
Seria necessário ter em mãos uma matriz que fosse
primitiva além de estocástica. Uma matriz primitiva é irredutível e aperiódica,
e assim o vetor de probabilidade estacionário existiria e seria único (pelo
teorema de Perron-Frobenius).
Esta segunda modificação resolveria o problema dos \textit{rank sinks}
que possuem ciclos.

A ideia que Brin e Page tiveram para solucionar este problema foi selecionar um
escalar $\alpha$ entre 0 e 1, que representa a probabilidade de seguir a estrutura
de \textit{links} representada em $S$. A matriz resultante, $G$, pode ser expressa
da seguinte maneira:

$$
G = \alpha S + (1 - \alpha)(1/n)ee'
$$

$G$ é chamada de \textit{Google matrix}. É interessante observá-la nos
seguintes aspectos:

\begin{itemize}
    \item $G$ é \textit{estocástica}, sendo combinação convexa de duas matrizes
        estocásticas $S$ e $E = (1/n)ee'$
    \item $G$ é \textit{irredutível}, pois cada página está diretamente
        conectada com qualquer outra.
    \item $G$ é \textit{aperiódica}, pois $G_{ii} > 0$ para todo $i$, quebrando
        a periodicidade.
\end{itemize}

A matriz $G$ é completamente densa, o que é indesejável do ponto de vista
computacional. No entanto ela pode ser escrita em função de $S$ que, por sua
vez, pode ser escrita em função de $H$, que é esparsa, nos garantindo que
podemos armazenar somente a matriz $H$

Finalmente, podemos escrever então

$$
\pi' = \pi'G
$$

Utilizando como exemplo o grafo da figura 2.2, e tomando $\alpha = 0.9$, temos a
seguinte matriz $G$:

$$
G = 0.9H + (0.9\begin{pmatrix} 0\\1\\0\\0\\0\\0\end{pmatrix} + 
            0.1\begin{pmatrix} 1\\1\\1\\1\\1\\1\end{pmatrix})
            1/6\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1\end{pmatrix}
$$

$$
G = \begin{pmatrix} 1/60 & 7/15 & 1/60 & 1/60 & 1/60 & 1/60\\
                    1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\
                    19/60 & 19/60 & 1/60 & 1/60 & 19/60 & 1/60\\
                    1/60 & 1/60 & 1/60 & 1/60 & 7/15 & 7/15\\
                    1/60 & 1/60 & 1/60 & 7/15 & 1/60 & 7/15\\
                    1/60 & 1/60 & 1/60 & 11/12 & 1/60 & 1/60\end{pmatrix}
$$

Podemos ver que o grafo representado por $G$ é completo se $\alpha \neq 1$.

\begin{center}
\includegraphics[scale=0.4]{grafo_exemplo_g.png}\\
\scriptsize{Figura 3.5: Grafo da figura 3.4 após as mudanças da matriz $S$ para
$G$.}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Implementação}

Computacionalmente, não há um algoritmo que determina com exatidão os números
do vetor $\pi$, portanto, utilizaremos um algoritmo iterativo, que aproxima
rapidamente o valor da distribuição estacionária. Este algoritmo é conhecido
como o método da potência, que calcula uma aproximação do autovetor associado
ao maior autovalor de $G$.
Neste caso, nosso autovetor é $\pi$ e o autovalor é 1.

A escolha do método da potência é dada pela necessidade de armazenar apenas a
matriz $H$ e dois vetores $\pi$ para a iteração, que são o atual e o anterior.
A matriz $G$ é acessada apenas pelos cálculos realizados.

Em particular, em nossa implementação, a matriz armazenada foi a $L$, em uma
lista de adjacência e mais um vetor que guarda o grau de saída de cada vértice.
No lugar de armazenar uma lista de adjacência de \texttt{double}, armazenamos
uma lista de \texttt{int} mais um vetor de \texttt{int}.

Tendo isso, pudemos implementar nosso \textit{PageRank} da seguinte forma:

\texttt{
  \begin{algorithmic}
    \STATE $res \gets 1$
    \STATE $pi \gets pi_0$\\
    \WHILE {$res \geqslant \epsilon$}
      \STATE $prev\_pi \gets pi$
      \STATE $pi' \gets pi' * G$
      \STATE $res \gets ||pi - prev\_pi||_1$
    \ENDWHILE
  \end{algorithmic}
}

É interessante notar que a linha onde é feita o produto vetor-matriz é calculada
da seguinte forma:

\begin{center}
  $G = \alpha S + (1 - \alpha)(1/n)ee'$\\
  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
  = \alpha(H + (1/n)ae') + (1 - \alpha)(1/n)ee'$\\
  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
  = \alpha H + (\alpha a + (1 - \alpha)e)(1/n)e'$
\end{center}

Como comentado acima, sendo necessárias apenas as informações contidas em $H$.

